package com.jeff.huawei.practice;

public class PredictWinner {
    public static boolean predictTheWinner(int[] nums) {
        // 调用递归函数，判断玩家 1 是否能获胜
        return score(nums, 0, nums.length - 1, 1) >= 0;
    }

    // 递归函数：计算从 nums[start...end] 区间中，当前玩家的最优得分差
    private static int score(int[] nums, int start, int end, int turn) {
        // 递归终止条件：数组为空
        if (start > end) {
            return 0;
        }

        // 如果是玩家 1 的回合，选择得分最大的策略（turn == 1）
        if (turn == 1) {
            return Math.max(
                nums[start] + score(nums, start + 1, end, -1),  // 取左端
                nums[end] + score(nums, start, end - 1, -1)    // 取右端
            );
        } else { // 如果是玩家 2 的回合，选择得分最小的策略（turn == -1）
            return Math.min(
                -nums[start] + score(nums, start + 1, end, 1),  // 取左端
                -nums[end] + score(nums, start, end - 1, 1)    // 取右端
            );
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {1, 5, 2};
        System.out.println(predictTheWinner(nums1)); // 输出: false

        int[] nums2 = {1, 5, 233, 7};
        System.out.println(predictTheWinner(nums2)); // 输出: true
    }
}
